package leetcode.nnumsum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Lc18 {


    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);

        for (int f = 0; f < nums.length - 3; f++) {
            if (f != 0 && nums[f] == nums[f - 1]) continue;
            if (0L + nums[f] + nums[f + 1] + nums[f + 2] + nums[f + 3] > target) break;
            for (int s = f + 1; s < nums.length - 2; s++) {
                if (0L + nums[f] + nums[s] + nums[s + 1] + nums[s + 2] > target) break;
                if (s != f + 1 && nums[s] == nums[s - 1]) continue;
                int l = s + 1;
                int r = nums.length - 1;
                long t = 0L + target - nums[f] - nums[s];
                while (l < r) {
                    if (nums[l] + nums[r] < t) l++;
                    else if (nums[l] + nums[r] > t) r--;
                    else {
                        ans.add(Arrays.asList(nums[f],nums[s],nums[l],nums[r]));
                        for (int numL = nums[l]; l < r && nums[l] == numL; l++);
                        for (int numR = nums[r]; l < r && nums[r] == numR; r--);
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Lc18 lc18 = new Lc18();
        int[] n = {1000000000,1000000000,1000000000,1000000000};
        System.out.println(lc18.fourSum(n, -294967296));

        System.out.println(1000000000 + 1000000000 + 1000000000 + 1000000000);
        long x = 1000000000L + 1000000000L + 1000000000L + 1000000000L;
        System.out.println(x);
    }
}
